#ifndef TRIE_INCLUDED
#define TRIE_INCLUDED
#include <vector>
template<class TStr,class T = int,const int hash_max = 3>
class Trie
{
private:
    std::vector<TStr> strings;
    class Node
    {
    public:
        unsigned int ch;
        Node* head[hash_max];
        Node* next;
        T* info;
        Node(unsigned int c = 0,Node* nt=0)
        {
            ch = c;
            fill(head,head+hash_max,(Node*)0);
            next=nt;
            info = 0;
        }
        ~Node()
        {
            for(int i=0;i<hash_max;i++) if(head[i])
                delete(head[i]);
            if(info) delete(info);
            if(next) delete(next);
        }
        Node* GetNext(unsigned int c,char opt= 'i')
        {
            int pos = c%hash_max;
            for(Node* nt=head[pos];nt;nt=nt->next) if(nt->ch==c)
            {
                return nt;
            }
            if(opt!='i') return 0;
            Node* nt = new Node(c,head[pos]);
            head[pos] = nt;
            return nt;
        }
    };
    Node* root;
public:
    Trie()
    {
        root = new Node();
    }
    ~Trie()
    {
        delete(root);
    }
    void Clear()
    {
        delete(root);
        root = new Node();
        strings.clear();
    }
    int Size()
    {
        return strings.size();
    }
    TStr& operator[] (int pos)
    {
        return strings[pos];
    }
    void Insert(const TStr& str,T info)
    {
        Node* p = root;
        for(int i=0,len(str.size());i<len;++i)
        {
            p = p->GetNext(str[i]);
        }
        if(!p->info)
        strings.push_back(str);
        *p->info = info;
    }
    int Find(const TStr& str)
    {
        Node* p = root;
        for(int i=0,len(str.size());i<len;++i)
        {
            p = p->GetNext(str[i],'F');
            if(!p) return false;
        }
        if(p->info) return true;
        else return false;
    }
    T Get(const TStr& str)
    {
        Node* p = root;
        for(int i=0,len(str.size());i<len;++i)
        {
            p = p->GetNext(str[i]);
        }
        return *p->info;
    }
};
#endif // TRIE_INCLUDED
